import java.util.*;
public class Text {
    /*
    //题目1：在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     */

    //哈希表法：时间复杂度为 O(N)
    //空间复杂度为 O(N)
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0 ; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[]{};
    }

     //暴力枚举法：时间复杂度为 O(N²)
     public int[] twoSum1(int[] nums, int target) {
         for(int i = 0; i < nums.length;i++){
             for(int j = i + 1 ;j < nums.length; j++){
                 if(nums[i] + nums[j] == target){
                     return new int[]{i,j};
                 }
             }
         }
         return new int[]{};
     }

     /*
     //题目二：两个按 非递减顺序 排列的整数数组nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     //
     //请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     //为了应对这种情况，nums1 的初始长度为 m + n
      */

     //先合并，后排序
     public void merge1(int[] nums1, int m, int[] nums2, int n) {
         for(int i = m;i<n + m;i++){
             nums1[i] = nums2[i - m];
         }
         Arrays.sort(nums1);
     }

     //双指针：
     //创建一个长度为 m + n 的新数组，这个像归并排序
     //时间复杂度为 O(m + n)
     //空间复杂度 O(m + n)
     public static void merge2(int[] nums1, int m, int[] nums2, int n) {
         int[] nums = new int[m + n];
         int index1 = 0;
         int index2 = 0;
         int index = 0;
         while(index1 < m && index2 < n){
             if(nums1[index1] <= nums2[index2]){
                 nums[index++] = nums1[index1++];
             }else{
                 nums[index++] = nums2[index2++];
             }
         }
         while(index1 < m){
             nums[index++] = nums1[index1++];
         }
         while(index2 < n){
             nums[index++] = nums2[index2++];
         }
         for(int i = 0; i < m + n; i++){
             nums1[i] = nums[i];
         }
     }

    //再一次进行优化
    //不再申请一个新的数组，而是直接在 nums1 上进行操作
    //采用指针从数组后面往前走的方式，将大的放在 nums1 后面
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int index1 = m -1;
        int index2 = n - 1;
        int cur = 0;
        while(index1 >= 0|| index2 >= 0){
            if(index1 == -1){
                cur = nums2[index2--];
            }else if(index2 == -1){
                cur = nums1[index1--];
            }else if(nums1[index1] >= nums2[index2]){
                cur = nums1[index1--];
            }else{
                cur = nums2[index2--];
            }
            nums1[index--] = cur;
        }
    }

    public static void main1(String[] args) {
        int[] nums1 = {0};
        int[] nums2 = {1};
        merge(nums1,0,nums2,1);
        System.out.println(Arrays.toString(nums1));
    }

    /*
    //复习
     */
    // 题目 1：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    //以下标 i 为结尾的连续数组的最大值是多少？
    //在这些最大值中，找最大值！
    public int maxSubArray(int[] nums) {
        int cur = 0;
        int maxAns = nums[0];
        for (int x : nums) {
            cur = Math.max(cur + x , x);
            maxAns = Math.max(cur,maxAns);
        }
        return maxAns;
    }

    /*
    //题目2 ： 两个数组的交集，输出结果中的每个元素一定是 唯一 的。
    //就是说就算 两个数组里 同一个数字重复出现，只算 1 次
     */
    public int[] intersection(int[] nums1, int[] nums2) {

        Set<Integer> set = new HashSet<>();
        for(int x : nums1){
            set.add(x);
        }

        Set<Integer> set1 = new HashSet<>();

        for(int x : nums2){
            if(set.contains(x)){
                set1.add(x);
            }
        }

        int index = 0;
        int[] nums = new int[set1.size()];
        for(int x : set1){
            nums[index++] = x;
        }

        return nums;
    }

    //两个数组的交集Ⅱ：
    //给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。
    // 返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。
    // 可以不考虑输出结果的顺序。
    //遍历两个数组，时间复杂度 O(m + n)
    //空间复杂度 ， O(min(m,n))

    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length){
            return intersect( nums2,  nums1);
        }

        Map<Integer,Integer> map = new HashMap<>();

        for(int x : nums1){
            if(map.get(x) == null){
                map.put(x,1);
            }else{
                int val = map.get(x);
                map.put(x,val + 1);
            }
        }

        int index = 0;
        int[] nums = new int[nums1.length];

        for(int x : nums2){
            if(map.get(x) != null && map.get(x) > 0){
                nums[index++] = x;
                int val = map.get(x);
                map.put(x,val - 1);
            }
        }

        //左闭右开！！
        return Arrays.copyOfRange(nums,0,index);
    }


    //罗马数字转整数
    public int romanToInt(String s) {
        int sum = 0;
        int i = 1;
        int pre = getValue(s.charAt(0));
        for(; i < s.length(); i++){
            int cur = getValue(s.charAt(i));
            if(pre < cur){
                sum -= pre;
            }else{
                sum += pre;
            }
            pre = cur;
        }
        return sum += pre;
    }

    private int getValue(char ch){
        switch(ch){
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }


    //盛最多水的容器
        public int maxArea(int[] height) {
            int left = 0;
            int right = height.length - 1;
            int max = 0;
            while (left < right) {
                int area = Math.min(height[left], height[right]) * (right - left);
                if (area > max) {
                    max = area;
                }
                if (height[left] < height[right]) {
                    left++;
                } else {
                    right--;
                }
            }
            return max;
        }


        /*
        //题目1 ：删除链表中倒数第k个节点，返回头节点
        //借助哑节点就能避免对特殊情况的考虑
         */
        class ListNode {
            int val;
            ListNode next;
            ListNode() {}
            ListNode(int val) { this.val = val; }
            ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

    //方法一：双指针法
        public ListNode removeNthFromEnd1(ListNode head, int n) {
            ListNode dummy = new ListNode(0,head);
            ListNode fast = head;
            ListNode slow = dummy;
            for(int i = 0; i < n ; i++){
                fast = fast.next;
            }

            while(fast != null){
                fast = fast.next;
                slow = slow.next;
            }

            slow.next = slow.next.next;
            ListNode cur = dummy.next;
            return cur;
        }

        //方法二：先遍历一遍链遍，求得长度 size
        //再遍历到 删除节点的前驱位置，进行删除即可
        public ListNode removeNthFromEnd2(ListNode head, int n) {
            int size = 0;
            ListNode cur = head;
            while (cur != null) {
                size++;
                cur = cur.next;
            }

            ListNode dummy = new ListNode(0, head);
            cur = dummy;
            for (int i = 1; i < size + 1 - n; i++) {
                cur = cur.next;
            }

            cur.next = cur.next.next;
            return dummy.next;
        }

        //方法三：利用栈
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0,head);
            Deque<ListNode> stack = new LinkedList<>();
            ListNode cur = dummy;
            while(cur != null){
                stack.push(cur);
                cur = cur.next;
            }
            for(int i = 0; i < n; i++){
                stack.pop();
            }

            cur = stack.pop();
            cur.next = cur.next.next;
            return dummy.next;
        }

        /*
        给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
        满足 i != j、i != k 且 j != k
        同时还满足 nums[i] + nums[j] + nums[k] == 0
        请你返回所有和为 0 且不重复的三元组。
         */
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> lists = new LinkedList<>();
            if(nums.length < 3){
                return lists;
            }
            Arrays.sort(nums);
            for(int i = 0; i < nums.length; i++){
                if(nums[i] > 0){
                    break;
                }
                if(i > 0 && nums[i] == nums[i - 1]){
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while(left < right){
                    int cur = nums[left] + nums[i] + nums[right];
                    if(cur == 0){
                        List<Integer> list = new LinkedList<>();
                        list.add(nums[i]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        lists.add(list);
                        while(left < right && nums[left] == nums[left + 1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right - 1]){
                            right--;
                        }
                        left++;
                        right--;

                    }else if(cur > 0){
                        right--;
                    }else{
                        left++;
                    }
                }
            }
            return lists;
        }

}
